密文搜索
题目 密文搜索
思路分析
在长度1024*1024的母串中 找n种长度为8的子串的全排列出现几次
暴力做的话 思路就是 把n个串的每个可能排列都在母串中find 注意一个问题 同一个子串可能在母串中出现多次 所以找到一个后不能立即退出 而是在找到的位置继续往后find n范围1000 长度为8 8的全排列有8!=40320种可能 也就是说共要枚举40320000次 还得find 肯定会超时 事实也是过了4/5
可以借鉴最小表示法的思路 用排序后的串表示串本身 然后直接哈希做
注意一个问题 最小表示法是在 循环同构的串的场景下 限制比这题要多些 这题是说任意顺序 也就是说 只要长度一定 出现的单词一样 就是合法的 而循环同构还有一个顺序的限制（只能以每个单词为开头的长度固定的串） 所以对于这题来说 只需要限制长度 做一遍sort 得到一个简化版的“最小表示法” 如果相同 就说明合法 ++
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
string og;
string tr[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> og;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tr[i];
}
LL cnt = 0;
for (int i = 0; i < n; i++) {
sort(tr[i].begin(), tr[i].end()); // 确保字符串按字典序排列，以便遍历所有排列
do {
size_t pos = og.find(tr[i], 0); // 从位置0开始搜索
while (pos != string::npos) { // 搜索整个字符串中的所有匹配
cnt++;
pos = og.find(tr[i], pos + 1); // 从下一个位置继续搜索 一个子串可能在模式串里出现多次 不能忽视这个
}
} while (next_permutation(tr[i].begin(), tr[i].end()));
}
cout << cnt;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int ans = 0;
string s;
int n;
map<string, int> m1;
cin >> s >> n;
if (s.size() < 8)
return 0;
for (int i = 0; i < n; i++) {
string s1;
cin >> s1;
sort(s1.begin(), s1.end());
m1[s1]++;//每个字符串都是键 值都是他们在后面n行中出现的次数
}
for (int i = 0; i < s.size() - 7; i++) {
string s2;
s2 = s.substr(i, 8); //每次从第i位开始切割切割8位
sort(s2.begin(), s2.end());
if (m1[s2]) { //在m1中搜索是否有相同的字符串
ans = ans + m1[s2];//这里加上该字符串键对应的值
}
}
cout << ans;
}
💬 评论